Field of the Invention
This invention relates to systems and methods for compressing data.
Background of the Invention
Software compression is very well understood and the source code for programs like GZIP are readily accessible in the public domain. The algorithm to implement compression is relatively complex to do in hardware for high bandwidth application given that the GZIP compression is based on the DEFLATE [2] algorithm and Huffman coding [3]. The idea behind compression is to use copy commands later in a data stream that appears earlier in the data stream. As such all compression implementations require a search history buffer and some type of compare length function to determine the longest length that can be used for the copy command. One method to implement the search matching in the previous history is to implement a hash function which maps the variable length string to fixed value which can be used to compare the data stream being compressed.
FIG. 1 represents a functional hardware block diagram of the compression algorithm for GZip. The input data 102 is hashed by a hash module 104 of a module 108 implementing, for example the LZ7/LZ78 algorithm. The hashed data is compared to generate a copy or literal command by the LZ CMD module 108 per Lempel-Ziv [4] algorithm or comparable algorithm. Once the statistics for the data to be compressed are gathered they are Huffman encoded and then compressed to be sent out as compressed output data 110.
The systems and methods disclosed herein provide an improved method for hashing input data.